package array
//最长公共子字符串
//例如: {"abc", "ab","abcdef"} 返回ab ;{"abc", "ab","c"} 返回空
func LongestCommonPrefix(strs []string)string{
	length:=len(strs)
	if length==0{
		return ""
	}
	//先把字符串转成字符rune
	first:=[]rune(strs[0])
	//定义变量
	var commonPrefix string
	//循环第一个字符串 , 主要是获取索引
	for i,_:=range first{
		//取出第一个字符串 , 到当前索引时的子串
		firstPrefix:=string(first[0:i+1])
		//判断是否有不相等的标志位
		flag:=true
		//循环所有的字符串数组
		for _,str:=range strs{
			//每次循环的时候置空一下
			//commonPrefix=""
			item:=[]rune(str)
			//取出每项 , 到当前索引的子串
			itemPrefix:=string(item[0:i+1])
			//如果有一个不相等就是flag false
			if firstPrefix!=itemPrefix{
				flag=false
			}
		}
		if flag{
			//赋值给结果
			commonPrefix= firstPrefix
		}else{
			return commonPrefix
		}
	}
	return commonPrefix
}
//最长无重复子串长度
//双指针法, left和right一前一后 , 遇到重复的就重新赋值left , 判断并存储最大长度值和当前的子串
//例如:输入 abcdefg  返回 abcdefg 7 ; 输入 abcacefga 返回 cefg 4
func LongestNorepeatSubstringLength(str string)(string,int){
	strRune:=[]rune(str)
	left:=0
	right:=0
	maxNum:=0
	m:=make(map[string]int)
	subStr:=""
	var flag =false
	//循环字符
	for i,item:=range strRune{
		key:=string(item)
		//right是当前索引
		right=i
		//看看有没有出现过
		if _,ok:=m[key];ok{
			//如果有出现过,获取下长度 , right肯定是当前非重复子串的下一个元素了
			num:=right-left
			//比最大值大的就替换
			if num>maxNum{
				subStr=string(strRune[left:right])
				maxNum=num
			}
			//left赋值当前索引
			left=i
			flag=true
		}
		//字符存到map
		m[key]=1
	}
	//如果一次也没重复的,就再算一次
	if !flag{
		maxNum=right-left+1
		subStr=string(strRune[left:right+1])
	}

	return subStr,maxNum
}